// 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
// 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

// 暴露接口
function restoreIpAddresses(s: string): string[] {
    const res: string[] = [];// 结果数组
    IpAddressesDFS(0, [], res, s);// 回溯算法
    return res;
};
// 辅助深度优先遍历函数
function IpAddressesDFS(start: number, subRes: string[], res: string[], s: string) {
    // DFS出口
    if (subRes.length === 4) {
        if (start === s.length) {// 字符串数组长度为4且已经遍历完
            res.push(subRes.join('.'));
            return;// 记得回溯
        } else {// 如果没有用完那就回溯
            return;
        }
    }
    // 回溯算法
    for (let i = 1; i <= 3; i++) {
        if (start + i - 1 >= s.length) {// 注意写法：切出的字符串下标超出上限直接返回
            return;
        }
        if (i != 1 && s[start] == '0') return;// IP格式规范，测试用例为例
        let currStr: string = s.slice(start, start + i);// 切出当前的字符串
        if (parseInt(currStr) > 255 || parseInt(currStr) < 0) {// 范围不满足仍然回溯
            return;
        }
        subRes.push(currStr);// 尝试将当前字符串加入子集
        start += i;// 头指针增加
        IpAddressesDFS(start, subRes, res, s);// 成功后继续递归遍历
        start -= i;// 注意：头指针记得也要撤销
        subRes.pop();// DFS失败，回溯，撤销选择
    }
}


// 这道题目属于非常经典的回溯算法的题目。
// 回溯算法一般用于在约束条件下，穷举所有节点，通常用于解决「找出所有可能的组合」问题。
// 通俗的理解回溯算法就是因为某一步的选择可能来到一个错误的状态，得不到正确的结果，
// 那么就不要往下做了，并撤销最后一个选择，回到选择前的状态，去试另一个选择。
// 求解回溯算法首先需要确定约束条件，这道题目中的约束条件分析可以得到：
// 1、一个子集片段的长度是 1~3
// 2、一个子集片段的范围是 0~255
// 3、一个子集不能是 "0x"、"0xx" 形式（这个是测试用例告诉我们的）
// 我们要用这些约束在DFS中充分地剪枝，规避掉一些选择，避免去搜索一些不会产生正确答案的分支。
// 之后需要确定回溯算法的目标：
// 1、我们的目标决定了我们 DFS 什么时候得到答案，什么时候撤销错误分支。
// 2、我们目标是生成 4 个有效片段，并且要用光 IP 字符串的字符。
// 3、当遍历的节点满足该条件时，说明已经生成了一个有效子集（字符串数组），推入结果数组。然后回溯，继续探索。
// 4、生成了4个有效片段，但没用光所有字符，不是有效的组合，不继续往下递归，直接返回，提前回溯。
// 通过上述规则即可拟定出算法搜索的框架，但要记得注意回溯算法的细节及分支处理。


